package tests;

import static org.junit.Assert.*;

import java.util.ArrayList;

import org.junit.Test;

import trees.RadixTree;

public class RadixTreeTest {

	@Test
	public void testConstructor() {
		RadixTree t;

		t = new RadixTree();
		assertFalse("tree contains root element abstraction error", t.contains(""));
		assertFalse("tree contains arbitrary symbol error", t.contains("\n"));
		assertFalse("tree contains arbitrary string error", t.contains("ALPHA"));
		assertFalse("tree contains arbitrary string error", t.contains("OMEGA"));
	}

	@Test
	public void testDepth() {
		RadixTree t;

		/* initial depth=0 test */
		t = new RadixTree();
		assertEquals("tree initialized depth error", 0, t.depth());

		/* simple depth=1 test */
		t = new RadixTree();
		t.insert("HELLO");
		assertEquals("tree insertion depth error", 1, t.depth());

		/* multi depth=1 test */
		t = new RadixTree();
		t.insert("HELLO");
		t.insert("BANZAI");
		t.insert("RAMJET");
		assertEquals("tree insertion depth error", 1, t.depth());

		/* nested depth test */
		t = new RadixTree();
		t.insert("HELLO");
		t.insert("HELL");
		assertEquals("tree insertion depth error", 2, t.depth());

		/* nested depth test */
		t = new RadixTree();
		t.insert("HELL");
		t.insert("HELLO");
		assertEquals("tree insertion depth error", 2, t.depth());
	}

	@Test
	public void testInsert() {
		RadixTree t;

		/* test disjoint multi insert */
		t = new RadixTree();
		t.insert("ALPHA");
		t.insert("BETA");
		assertTrue("disjoint multi insertion fail", t.contains("ALPHA"));
		assertTrue("disjoint multi insertion fail", t.contains("BETA"));
		assertFalse("disjoint multi insertion fail", t.contains("CHARLIE"));

		/* test matching prefix multi insert */
		t = new RadixTree();
		t.insert("HUMMINGBIRD");
		t.insert("HUMMER");
		assertTrue("matching prefix insertion fail", t.contains("HUMMER"));
		assertTrue("matching prefix insertion fail", t.contains("HUMMINGBIRD"));
		assertFalse("matching prefix insertion fail", t.contains("HUMM"));

		/* test fully matching prefix multi insert */
		t = new RadixTree();
		t.insert("HUMMINGBIRD");
		t.insert("HUMM");
		assertTrue("fully matching insertion fail", t.contains("HUMM"));
		assertTrue("fully matching insertion fail", t.contains("HUMMINGBIRD"));

		/* test fully matching prefix multi insert reverse order */
		t = new RadixTree();
		t.insert("HUMM");
		t.insert("HUMMINGBIRD");
		assertTrue("fully matching insertion fail", t.contains("HUMM"));
		assertTrue("fully matching insertion fail", t.contains("HUMMINGBIRD"));
		

		/* test thorough miscellaneous*/
		t = new RadixTree();
		t.insert("CANNON");
		t.insert("CANNER");
		t.insert("BARD");
		t.insert("HAMMER");
		t.insert("HAMPER");
		t.insert("CANNERIES");
		t.insert("CANNERY");
		assertTrue("fully matching insertion fail", t.contains("HAMMER"));
		assertTrue("fully matching insertion fail", t.contains("HAMPER"));
		assertTrue("fully matching insertion fail", t.contains("BARD"));
		assertTrue("fully matching insertion fail", t.contains("CANNER"));
		assertTrue("fully matching insertion fail", t.contains("CANNON"));
		assertTrue("fully matching insertion fail", t.contains("CANNERY"));
		assertTrue("fully matching insertion fail", t.contains("CANNERIES"));
		assertFalse("fully matching insertion fail", t.contains("CANN"));
		assertFalse("fully matching insertion fail", t.contains("HAM"));
		assertFalse("fully matching insertion fail", t.contains("HAM"));
	}

	@Test
	public void treeStressTestUniformDepth() {
		RadixTree t;
		Iterable i;
		String[] prefixSet;
		String[] rootSet;
		int length;

		/* test disjoint multi insert */
		t = new RadixTree();
		prefixSet = new String[]{"PRE", "POST", "INTER", "SUPER", "EXTRA"};
		rootSet = new String[]{"RATE", "DESERVE", "RELATE", "OPERATION"};
		ArrayList<String> list = new ArrayList<String>();
		length = 0;
		for (String prefix : prefixSet) {
			for (String root : rootSet) {
				list.add(prefix + root);
				t.insert(prefix + root);
				length ++;
			}
		}
		i = t.iterator();
		for (Object s : i) {
			assertTrue("missing inserted element from iterator", list.contains(s));
			length --;
		}

		assertEquals("Iterator length fail", 0, length);
		assertEquals("Stress test depth fail", 4, t.depth());
	}
	
	@Test
	public void testIterator() {
		RadixTree t;
		Iterable i;
		String[] testSet;
		int length;

		/* test disjoint multi insert */
		t = new RadixTree();
		testSet = new String[]{"ALPHA", "BETA", "CANNON", "CANNER", "BARD", "HAMMER", "HAMPER", "CANNERIES", "CANNERY"};
		ArrayList<String> list = new ArrayList<String>();
		length = 0;
		for (String s : testSet) {
			list.add(s);
			t.insert(s);
		}
		i = t.iterator();
		for (Object s : i) {
			assertTrue("Inserted element missing from iterator", list.contains(s));
			length ++;
		}

		assertEquals("Iterator length fail", testSet.length, length);
	}

	@Test
	public void testRemove() {
		RadixTree t;

		/* test initialization size */
		t = new RadixTree();
		assertEquals("incorrect null remove", null, t.remove("ANYTHING"));

		/* test disjoint multi insert-remove */
		t = new RadixTree();
		t.insert("ALPHA");
		t.insert("BETA");
		assertEquals("remove fail", "BETA", t.remove("BETA"));
		assertEquals("remove depth fail", 1, t.depth());
		
		/* test disjoint multi insert size */
		t = new RadixTree();
		t.insert("ALPHA");
		t.insert("BETA");
		t.insert("BEAKER");
		t.insert("LAP");
		t.insert("LAPPER");
		t.insert("LAPPING");
		assertEquals("remove fail", "BETA", t.remove("BETA"));
		assertEquals("remove fail", null, t.remove("BETA"));
		assertEquals("remove fail", "LAP", t.remove("LAP"));
		assertEquals("remove fail", null, t.remove("LAP"));
		//TODO make sure the tree is being updated for optimal overlap of strings
//		System.out.println(t);
//		System.out.println(t.iterator());
	}

	@Test
	public void testSize() {
		RadixTree t;

		/* test initialization size */
		t = new RadixTree();
		assertEquals("initalization size fail", 0, t.size());

		/* test disjoint multi insert size */
		t = new RadixTree();
		t.insert("ALPHA");
		t.insert("BETA");
		assertEquals("insertion size fail", 2, t.size());

		/* test matching prefix  insert size */
		t = new RadixTree();
		t.insert("HUMMINGBIRD");
		t.insert("HUMMER");
		assertEquals("insertion size fail", 2, t.size());

		/* test thorough miscellaneous*/
		t = new RadixTree();
		t.insert("CANNON");
		t.insert("CANNER");
		t.insert("BARD");
		t.insert("HAMMER");
		t.insert("HAMPER");
		t.insert("CANNERIES");
		t.insert("CANNERY");
		assertEquals("insertion size fail", 7, t.size());
	}

}
